Beliau dilahirkan sebagai Sebastián Moyano di wilayah Córdoba, Sepanyol, pada tahun 1479 atau 1480. Beliau menggunakan nama Belalcázar sempena nama istana kota yang terletak berdekatan dengan tempat kelahiran beliau di Córdoba. Berdasarkan pada pelbagai sumber, beliau mungkin berlayar ke Dunia Baru bersama dengan Christopher Columbus seawal tahun 1498, tetapi Juan de Castellanos telah menulis bahawa beliau telah membunuh seekor baghal pada tahun 1507, dan melarikan diri dari Sepanyol untuk ke Hindia Barat kerana takut dihukum, dan sebagai satu peluang untuk keluar daripada kemiskinan yang dihadapi oleh beliau.